//
// Created by Tan Ke on 2024/2/13.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>


/*
 * 从字符串的最左边开始遍历到字符串的最右边, 假设每次迭代的下标索引 i 为回文字符串的中点, 那么有三种情况:
 *
 * 1. 以 i 为中心的奇数长度的回文;
 * 2. 以 i 为中心-1的偶数长度的回文;
 * 3. 以 i 为中心+1的偶数长度的回文;
 *
 * 从这三种情况中得出最长的长度回文, 就是以下标 i 为回文字符串中点的最长回文
 *
 * 当遍历完后, 就能得到最长的回文子字符串
 *
 * 注意的是: 如果遍历到 i 离两边端点的最小长度, 都小于之前遍历的最长回文长度, 那么就不用再遍历了
 *
 */

int subPalHelper(char* s, int i, int* startIndex, int* endIndex)
{
    /* 第一种情况, 以 i 为中心的奇数长度的回文 */
    int leftIndex1 = i - 1;
    int rightIndex1 = i + 1;
    int len1 = 0;

    while (leftIndex1 >= 0 && rightIndex1 < strlen(s) && s[leftIndex1] == s[rightIndex1]) {
        leftIndex1 -= 1;
        rightIndex1 += 1;
        len1 += 2;
    }
    leftIndex1 += 1;
    rightIndex1 -= 1;

    if (len1 > 0) {
        len1 += 1;
    }

    /* 第二种情况, 以 i 为中心-1的偶数长度的回文 */
    int leftIndex2 = i;
    int rightIndex2 = i + 1;
    int len2 = 0;

    while (leftIndex2 >= 0 && rightIndex2 < strlen(s) && s[leftIndex2] == s[rightIndex2]) {
        leftIndex2 -= 1;
        rightIndex2 += 1;
        len2 += 2;
    }
    leftIndex2 += 1;
    rightIndex2 -= 1;

    /* 第三种情况, 以 i 为中心+1的偶数长度的回文 */
    int leftIndex3 = i - 1;
    int rightIndex3 = i;
    int len3 = 0;

    while (leftIndex3 >= 0 && rightIndex3 < strlen(s) && s[leftIndex3] == s[rightIndex3]) {
        leftIndex3 -= 1;
        rightIndex3 += 1;
        len3 += 2;
    }

    leftIndex3 += 1;
    rightIndex3 -= 1;

    if (len1 > len2 && len1 > len3) {
        *startIndex = leftIndex1;
        *endIndex = rightIndex1;
        return len1;
    }
    if (len2 > len1 && len2 > len3) {
        *startIndex = leftIndex2;
        *endIndex = rightIndex2;
        return len2;
    }

    *startIndex = leftIndex3;
    *endIndex = rightIndex3;
    return len3;
}

char* longestPalindrome(char* s)
{
    int startIndex = 0;
    int endIndex = 0;
    int len = 0;

    if (strlen(s) == 1) {
        return s;
    }

    for (int i = 0; i < strlen(s); i ++) {
        int subPalStartIndex = 0;
        int subPalEndIndex = 0;

#if 0
        int leftLent = (i + 1) < (strlen(s) - i + 2) ? (i + 1) : (strlen(s) - i + 2);
        if (len > leftLent) {
            break;
        }
#endif

        int subPalLen = subPalHelper(s, i, &subPalStartIndex, &subPalEndIndex);

        if (subPalLen > len) {
            len = subPalLen;
            startIndex = subPalStartIndex;
            endIndex = subPalEndIndex;
        }
    }

    if (len == 0) {
        len = 1;
    }

    char* result = (char*)malloc((len + 1));
    memset(result, 0, (len + 1));
    memcpy(result, s + startIndex, len);
    return result;
}


int main(void)
{
#if 0
    char* s1 = "babad";
    printf("%s\n", longestPalindrome(s1));

    char* s2 = "cbbd";
    printf("%s\n", longestPalindrome(s2));
#endif
    char* s3 = "aaaaa";
    printf("%s\n", longestPalindrome(s3));
    return 0;
}